#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;


/***
 *
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。
 * 将这两数相加会返回一个新的链表。

  你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * **/

ListNode *reverse(ListNode *head) {

    if (head == nullptr || head->next == nullptr)
        return head;

    auto ret = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    //1 2 3 4
    return ret;
}

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {

    /// 7 2 4 3
    //  5 6 4
    //________
    // 3 4 2 7
    // 4 6 5
    //___________
    // 7 0 8 7
    //------------

    //

    auto l11 = reverse(l1);
    auto l22 = reverse(l2);

    ListNode *ret = new ListNode();
    auto dummp = ret;
    int left = 0;//余数
    while (l11 && l22) {
        int sum = l11->val + l22->val + left;
        ret->next = new ListNode(sum % 10);
        ret = ret->next;

        left = sum / 10;

        l11 = l11->next;
        l22 = l22->next;
    }

    while (l11) {
        int sum = l11->val + left;
        ret->next = new ListNode(sum % 10);
        ret = ret->next;

        left = sum / 10;

        l11 = l11->next;
        // l22=l22->next;
    }

    while (l22) {
        int sum = l22->val + left;
        ret->next = new ListNode(sum % 10);
        ret = ret->next;

        left = sum / 10;

        //l11=l11->next;
        l22 = l22->next;
    }

    if (left > 0)
        ret->next = new ListNode(left);


    return reverse(dummp->next);

}